package leetcode.array;

/*
4. 寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000

提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-10^6 <= nums1[i], nums2[i] <= 10^6
*/

import java.util.*;

public class FindMedianSortedArrays4 {
    public static void main(String[] args) {
//        int[] nums1 = new int[]{1,3};
//        int[] nums2 = new int[]{2};

//        int[] nums1 = new int[]{1,2};
//        int[] nums2 = new int[]{3,4};

//        int[] nums1 = new int[]{};
//        int[] nums2 = new int[]{1};

//        int[] nums1 = new int[]{0,0,0,0,0};
//        int[] nums2 = new int[]{-1,0,0,0,0,0,1};

        int[] nums1 = new int[]{1,1};
        int[] nums2 = new int[]{1,2};

        System.out.println(Arrays.toString(nums1));
        System.out.println(Arrays.toString(nums2));
        System.out.println(test(nums1, nums2));
    }

    private static double test(int[] nums1, int[] nums2) {
        int[] nums = null;
        if(0 == nums1.length && 0 != nums2.length)
            nums = nums2;
        else if(0 != nums1.length && 0 == nums2.length)
            nums = nums1;

        if(null != nums)
            if(0 == nums.length%2) {
                double sum = nums[nums.length/2 - 1] + nums[nums.length/2];
                return sum/2;
            }
            else
                return nums[nums.length/2];

        nums = Arrays.copyOf(nums1,nums1.length + nums2.length);
        for(int i = 0, j = nums1.length; i < nums2.length; i++, j++)
            nums[j] = nums2[i];

        Arrays.sort(nums);

        if(0 == nums.length%2) {
            double sum = nums[nums.length/2 - 1] + nums[nums.length/2];
            return sum/2;
        }
        else
            return nums[nums.length/2];
    }
}
